<html>

<head>
  <meta http-equiv="Content-Type" content="text/html; charset=utf-8"> 
  <link rel="stylesheet" title="Default" href="http://acm.math.spbu.ru/~sk1/colorer/my.css">

  <script src="http://acm.math.spbu.ru/~sk1/colorer/highlight.js"></script>
  <script src="http://acm.math.spbu.ru/~sk1/colorer/cpp.js"></script>
  <script>hljs.initHighlightingOnLoad();</script>
</head>

<body>

<pre><code>
/**
 * Author: Sergey Kopeliovich (Burunduk30@gmail.com)
 * Date: 2013.02.24
 */

#include &lt;cstdio&gt;
#include &lt;cstring&gt;
#include &lt;cassert&gt;
#include &lt;algorithm&gt;
#include &lt;vector&gt;

using namespace std;

#define forn(i, n) for (int i = 0; i &lt; (int)(n); i++)
#define fornd(i, n) for (int i = (int)(n) - 1; i &gt;= 0; i--)
#define pb push_back
#define sz(a) (int)(a).size()

const int maxN = 1000;

int n, k, f[maxN][maxN], g[maxN][maxN];
vector &lt;int&gt; c[maxN], ind[maxN];
int _pr[maxN], _pre[maxN], size[maxN];
int rn, r[maxN];

inline void relax( int &a, int b )
{
  a = min(a, b);
}

void go( int v, int pr, int pre )
{
  int x, last = -1;
  _pr[v] = pr, _pre[v] = pre;
  size[v] = 1;
  forn(i, sz(c[v]))
    if ((x = c[v][i]) != pr)
    {
      go(x, v, ind[v][i]);
      if (last == -1)
      {
        g[x][0] = 1;
        forn(i, n - 1)
          g[x][i + 1] = f[x][i];
      }
      else
        forn(i, size[v])
        {
          forn(j, size[x])
            relax(g[x][i + j + 1], g[last][i] + f[x][j]);
          relax(g[x][i], g[last][i] + 1);
        }
      last = x;
      size[v] += size[x];
    }
  if (last == -1)
    f[v][0] = 0;
  else
    forn(i, n)
      f[v][i] = g[last][i];
}

void recover( int v, int k )
{
  int x = -1, xe = -1, last;
  fornd(i, sz(c[v]))
    if ((last = c[v][i]) != _pr[v])
    {
      if (x != -1)
        if (g[x][k] == g[last][k] + 1)
          r[rn++] = xe;
        else
          forn(i, k)
            if (g[x][k] == g[last][i] + f[x][k - i - 1])
              recover(x, k - i - 1), k = i;
      x = last, xe = ind[v][i];
    }
  if (x != -1)
    if (k == 0)
      r[rn++] = xe;
    else
      recover(x, k - 1);
}

int main()
{
  #define NAME "tree"
  assert(freopen(NAME ".in", "r", stdin));
  assert(freopen(NAME ".out", "w", stdout));

  assert(scanf("%d%d", &n, &k) == 2 && 1 &lt;= k && k &lt;= n && n &lt;= maxN);
  forn(i, n - 1)
  {
    int a, b;
    assert(scanf("%d%d", &a, &b) == 2);
    a--, b--;
    c[a].pb(b), c[b].pb(a);
    ind[a].pb(i), ind[b].pb(i);
  }
  memset(f, 0x30, sizeof(f));
  memset(g, 0x30, sizeof(g));
  go(0, -1, -1);

  int tmp, ri = 0, ma = f[0][k - 1];
  for (int i = 1; i &lt; n; i++)
    if (ma &gt; (tmp = f[i][k - 1] + 1))
      ma = tmp, ri = i;
  printf("%d\n", ma);

  if (ri)
    r[rn++] = _pre[ri];
  recover(ri, k - 1);
  sort(r, r + rn);
  forn(i, rn)
    printf("%d%c", r[i] + 1, " \n"[i == rn - 1]);
  return 0;
}

</code></pre>

</body>
</html>

<font style="visibility:hidden">
